/*
 *希尔排序
 */
#include<iostream>
#include<vector>
using namespace std;

void shell_sort(vector<int> &nums)
{
    /*  另一种算增量序列的方法
    int gap=1;
    while(gap<nums.size()/3){
        gap=gap*3+1;
    }
    */
    int gap=nums.size()/2;
    while(gap>=1){
        for(int i=gap;i<nums.size();++i)
        {
            for(int j=i;j>=gap&&nums[j]<nums[j-gap];j=j-gap){//注意j>=gap
                int tmp=nums[j];
                nums[j]=nums[j-gap];
                nums[j-gap]=tmp;
            }
        }
        gap/=2;
        //gap/=3;
    }
    
}
int main()
{
    vector<int> nums={1,2,15,0,5,34};
    shell_sort(nums);
    for(auto num:nums)
    {
        cout<<num<<" ";
    }
    return 0;
}